{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 31.3 Modular arithmetic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.3-1\n",
    "\n",
    "> Draw the group operation tables for the groups $(\\mathbb{Z}_4, +_4)$ and $(\\mathbb{Z}_5^*, \\cdot_5)$. Show that these groups are isomorphic by exhibiting a one-to-one correspondence $\\alpha$ between their elements such that $a + b \\equiv c ~(\\text{mod}~4)$ if and only if $\\alpha(a) \\cdot \\alpha(b) \\equiv \\alpha(c) ~(\\text{mod}~5)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $(\\mathbb{Z}_4, +_4)$: $\\{ 0, 1, 2, 3 \\}$.\n",
    "* $(\\mathbb{Z}_5^*, \\cdot_5)$: $\\{ 1,2,3,4 \\}$.\n",
    "\n",
    "$\\alpha(x) = 2^{x-1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.3-2\n",
    "\n",
    "> List all subgroups of $\\mathbb{Z}_9$ and of $\\mathbb{Z}_{13}^*$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $\\mathbb{Z}_9$\n",
    "   * $\\langle 0 \\rangle = \\{ 0 \\}$,\n",
    "   * $\\langle 1 \\rangle = \\{ 0, 1, 2, 3, 4, 5, 6, 7, 8 \\}$,\n",
    "   * $\\langle 2 \\rangle = \\{ 0, 2, 4, 6, 8 \\}$.\n",
    "* $\\mathbb{Z}_{13}^*$\n",
    "   * $\\langle 1 \\rangle = \\{ 1 \\}$,\n",
    "   * $\\langle 2 \\rangle = \\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.3-3\n",
    "\n",
    "> Prove Theorem 31.14.\n",
    "\n",
    "> A nonempty closed subset of a finite group is a subgroup."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Closure: the subset is closed.\n",
    "* Identity: suppose $a \\in S'$, then $a^{(k)} \\in S'$. Since the subset is finite, there must be a period such that $a^{(m)} = a^{(n)}$, hence $a^{(m)}a^{(-n)} = a^{(m - n)} = 1$, therefore the subset must contain the identity.\n",
    "* Associativity: inherit from the origin group.\n",
    "* Inverses: suppose $a^{(k)} = 1$, the inverse of element $a$ is $a^{(k-1)}$ since $aa^{(k-1)}=a^{(k)}=1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.3-4\n",
    "\n",
    "> Show that if $p$ is prime and $e$ is a positive integer, then\n",
    "\n",
    "> $\\phi(p^e) = p^{e-1}(p - 1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\phi(p^e) = p^e \\cdot \\left ( 1 - \\frac{1}{p} \\right ) = p^{e-1}(p - 1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.3-5\n",
    "\n",
    "> Show that for any integer $n > 1$ and for any $a \\in \\mathbb{Z}_n^*$, the function $f_a : \\mathbb{Z}_n^* \\rightarrow \\mathbb{Z}_n^*$ defined by $f_a(x) = ax ~\\text{mod}~ n$ is a permutation of $\\mathbb{Z}_n^*$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To prove it is a permutation, we need to prove that \n",
    "* for each element $x \\in \\mathbb{Z}_n^*$, $f_a(x) \\in \\mathbb{Z}_n^*$,\n",
    "* the numbers generated by $f_a$ are distinct.\n",
    "\n",
    "Since $a \\in \\mathbb{Z}_{n}^*$ and $x \\in \\mathbb{Z}_n^*$, then $f_a(x) = ax ~\\text{mod}~ n \\in \\mathbb{Z}_n^*$ by the closure property. \n",
    "\n",
    "Suppose there are two distinct numbers $x \\in \\mathbb{Z}_n^*$ and $y \\in \\mathbb{Z}_n^*$ that $f_a(x) = f_a(y)$,\n",
    "\n",
    "$$\n",
    "\\begin{array}{rlll}\n",
    "f_a(x) &=& f_a(y) \\\\\n",
    "ax ~\\text{mod}~ n &=& ay ~\\text{mod}~ n \\\\\n",
    "(a ~\\text{mod}~ n)(x ~\\text{mod}~ n) &=& (a ~\\text{mod}~ n)(y ~\\text{mod}~ n) \\\\\n",
    "(x ~\\text{mod}~ n) &=& (y ~\\text{mod}~ n) \\\\\n",
    "x &\\equiv& y & (\\text{mod}~n)\n",
    "\\end{array}\n",
    "$$\n",
    "which contradicts the assumption, therefore the numbers generated by $f_a$ are distinct."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
